package com.cqs;

import java.util.*;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.stream.Collectors;

public class MultiBags {

    /**
     * 贪心算法不能保证全局最优解
     *
     * @param goods
     * @param cap
     * @return
     */
    public List<Integer> greedy(Integer[] goods, int cap) {
        Arrays.sort(goods, Collections.reverseOrder());
        List<Integer> bags = new ArrayList<>();
        //每个箱子装的使用情况
        List<Map<Integer, Integer>> bagsHelper = new ArrayList<>();
        for (int i = 0; i < goods.length; i++) {
            int bagSize = bags.size();
            boolean handled = false;
            for (int j = 0; j < bagSize; j++) {
                int curBag = bags.get(j);
                if (cap - curBag >= goods[i]) {
                    bags.remove(j);
                    bags.add(j, curBag + goods[i]);
                    handled = true;
                    Map<Integer, Integer> map = bagsHelper.get(j);
                    map.put(goods[i], map.getOrDefault(goods[i], 0) + 1);
                    break;
                }
            }
            if (!handled) {
                bags.add(goods[i]);
                Map<Integer, Integer> map = new HashMap<>();
                map.put(goods[i], 1);
                bagsHelper.add(map);
            }
        }

        System.out.println("" + bagsHelper);
        return bags;
    }

    public static void main(String[] args) {
        MultiBags minimumBox = new MultiBags();
        int cap = 524;
        Map<Integer, Integer> goodMap = new LinkedHashMap<>();
        goodMap.put(442, 1);
        goodMap.put(252, 7);
        goodMap.put(127, 5);
        goodMap.put(106, 4);
        goodMap.put(85, 1);
        goodMap.put(84, 1);
        goodMap.put(46, 1);
        goodMap.put(37, 2);
        goodMap.put(12, 3);
        goodMap.put(10, 6);
        goodMap.put(9, 2);
        Integer[] goods = new Integer[goodMap.values().stream().reduce(Integer::sum).orElse(0)];
        AtomicInteger count = new AtomicInteger(-1);
        //初始化数组
        goodMap.forEach((good, num) -> {
            for (int i = 0; i < num; i++) {
                goods[count.addAndGet(1)] = good;
            }
        });
        System.out.println("货物:" + goodMap + "\n转化为数组:" + Arrays.stream(goods).collect(Collectors.toList()));
        System.out.println("货物总重量: " + Arrays.stream(goods).reduce(Integer::sum).orElse(0));
        List<Integer> greey = minimumBox.greedy(goods, cap);
        System.out.println(greey + " 箱子货物总量:" + greey.stream().reduce(Integer::sum).get());
    }
}